
let num = [4, 1, 3, 2, 5, 8, 10, 7, 6, 9];

// 冒泡排序
const bubbleSort = () => {
  for (let i = 0; i < num.length - 1; i++) {
    for (let j = 0; j < num.length - 1 - i; j++) {
      if (num[j] > num[j+1]) {
        [num[j+1], num[j]] = [num[j], num[j+1]];
      }
    }
  }
  return num;
}

const bubbleSort2 = arr => {
  for (let i = 0; i < arr.length-1; i++) {
    let hasChange = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j+1], arr[j]] = [arr[j], arr[j+1]]
        hasChange = true;
      }
    }
    // 当一次循环没有发生数据交换，则表示完成排序
    if (!hasChange) break;
  }
  return arr;
}


// 插入排序
const insertSort = arr => {
  let j;
  let temp;
  for (let i = 1; i < arr.length; i++) {
    j = i;
    // 保存当前的值
    temp = arr[i]
    // 当索引大于0 且 前一个值大于后一个值时
    while(j > 0 && arr[j-1] > temp) {
      // 把前一个值赋值给后一个，
      arr[j] = arr[j-1];
      // 往前移一位，继续比较
      j --
    }
    // 当找到自己的位置时，插入当前的值
    arr[j] = temp;
  }
  return arr;
}

// 归并排序
const mergeSort = arr => {
  return mergeSortRec(arr);
}

const mergeSortRec = arr => {
  const length = arr.length;
  if (length === 1) {
    return arr;
  }
  let mid = Math.floor(length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid, length);
  return merge(mergeSortRec(left), mergeSortRec(right));
}

const merge = (left, right) => {
  const result = [];
  while(left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) {
    result.push(left.shift());
  }

  while (right.length) {
    result.push(right.shift())
  };

  return result;
}

// 快速排序
const quickSort = arr => {
  if (arr.length <=1) return arr;
  const midIndex = Math.floor(arr.length / 2);
  const val = arr.splice(midIndex, 1);
  const midVal = val[0];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > midVal) {
      right.push(arr[i]);
    } else {
      left.push(arr[i]);
    }
  }

  return quickSort(left).concat(midVal, quickSort(right));

}

// 希尔排序
const shellSort = arr => {
  let len = arr.length;
  let gap = len;
  let temp;
  while(gap < len / 3) {
    // 动态的定义间隔序列
    gap = gap * 3 + 1
  }

  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i];
    }
  }
}






